# -*- coding: utf-8 -*-
# @Author: bao
# @Date:   2017-01-24 10:27:26
# @Last Modified by:   bao
# @Last Modified time: 2017-05-15 10:30:13

import networkx as nx
from datetime import datetime


def k_cycle_network(switch_nums, degree):
    """
    @ static connected network
    @ cycle graph
    """
    match_results = {}
    for x in range(1, degree + 1):
        match = []
        for src in range(1, switch_nums + 1):
            dst = (src + x - 1) % switch_nums + 1 + switch_nums
            match.append((src, dst))
        match_results[x] = match
    return match_results


def k_regular_network(switch_nums, degree, connected=True):
    """
    Generate k regular graph
    @ degree: dynamic links
    @ return match_results {k:[(src1,dst1),(src2,dst2)]}
    """
    regular_graph = nx.random_regular_graph(degree, switch_nums)  # node id starts from 0
    if connected:
        while not nx.is_connected(regular_graph):
            regular_graph = nx.random_regular_graph(degree, switch_nums)

    bp_src = range(1, switch_nums + 1)
    bp_dst = range(switch_nums + 1, switch_nums * 2 + 1)

    match_results = bipartite_matchings(regular_graph, bp_src, bp_dst, degree, switch_nums)
    return match_results


def bipartite_matchings(graph, bp_src, bp_dst, degree, switch_nums):
    """
    Calculate k matchings
    {k:[(src1,dst1), (src2,dst2), (src3,dst3)...]}
    """
    startTime = datetime.now()
    # Transform the graph to bipartite graph
    bp_graph = nx.Graph()
    bp_graph.add_nodes_from(bp_src, bipartite=0)
    bp_graph.add_nodes_from(bp_dst, bipartite=1)

    for edge in list(graph.edges()):
        bp_graph.add_edge(edge[0] + 1, edge[1] + switch_nums + 1)
        bp_graph.add_edge(edge[1] + 1, edge[0] + switch_nums + 1)

    # Decompose the graph to k matchings
    match_results = {}  # port num: matching
    for x in xrange(1, degree + 1):
        match = nx.bipartite.maximum_matching(bp_graph)
        # print ("match", x, match)
        temp_match = []
        for src, dst in match.items():
            if src > switch_nums:
                break
            temp_match.append((src, dst))
            bp_graph.remove_edge(src, dst)
        match_results[x] = temp_match
    endTime = datetime.now()
    timeDiff = endTime - startTime
    # print ('bipartite_matchings %d.' %timeDiff.seconds,'%ds' %timeDiff.microseconds)
    return match_results
